﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
// 原题连接：https://leetcode.cn/problems/maximum-length-of-repeated-subarray/
/*
题目描述：
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

 

示例 1：
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。

示例 2：
输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5
 

提示：
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 100
*/

// 开始解题：
// 方法2——动态规划
int findLength(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int** dp = (int**)malloc((nums1Size + 1) * sizeof(int*));
    if (NULL == dp) {
        perror("malloc fail");
        exit(-1);
    }
    int i = 0;
    for (i = 0; i <= nums1Size; i++) {
        dp[i] = (int*)malloc((nums2Size + 1) * sizeof(int));
        if (NULL == dp[i]) {
            perror("malloc fail");
            exit(-1);
        }
    }
    int j = 0;
    for (i = 0; i <= nums1Size; i++) {
        for (j = 0; j <= nums2Size; j++) {
            dp[i][j] = 0;
        }
    }
    int answer = 0;
    for (i = nums1Size - 1; i >= 0; i--) {
        for (j = nums2Size - 1; j >= 0; j--) {
            dp[i][j] = nums1[i] == nums2[j] ? dp[i + 1][j + 1] + 1 : 0;
            if (dp[i][j] > answer) {
                answer = dp[i][j];
            }
        }
    }
    return answer;
}
// 时间复杂度：O(nm)，其中n和m分别为nums1数组和num2数组的长度。
// 空间复杂度：O(nm)，我们需要额外的nm个空间来存储dp的数据，故空间复杂度为O(nm)。